home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / oper_sys / emerald / emrldsys.lha / Language / Compiler / set.c < prev    next >
Encoding:
C/C++ Source or Header  |  1990-08-16  |  5.9 KB  |  285 lines
  1. /*
  2.  * @(#)set.c    1.3  7/9/87
  3.  */
  4. /* Copyright 1986 Norm Hutchinson.     May not be used for any         *
  5.  * purpose without written permission from the author.               */
  6.  
  7. #include "assert.h"
  8. #include "system.h"
  9. #include "set.h"
  10.  
  11. #define INITIALSIZE 4
  12.  
  13. #define HASH(key, set) (((key) ^ ((key) >> 4)) & set->maxIndex)
  14. static void SetCheckOutHashTable();
  15.  
  16. Set Set_Create()
  17. {
  18.   register int i;
  19.   register Set m;
  20.  
  21.   m = (Set) malloc(sizeof(SetRecord));
  22.   m->maxIndex = INITIALSIZE - 1;
  23.   m->maxCount = m->maxIndex - (m->maxIndex >> 2); /* Max fill 87.5 % */
  24.   m->count = 0;
  25.   m->table = (STEPtr) malloc(INITIALSIZE * sizeof(STE));
  26.   for (i = 0; i < INITIALSIZE; i++) {
  27.     m->table[i].key = NIL;
  28.   }
  29. #ifdef DEBUGSET
  30.       SetCheckOutHashTable(m);
  31. #endif DEBUGSET
  32.   return(m);
  33. }
  34.  
  35. Set Set_CreateSized(fCount)
  36. int fCount;
  37. {
  38.   register int i;
  39.   register Set m;
  40.  
  41.   assert(fCount > 0);
  42.   m = (Set) malloc(sizeof(SetRecord));
  43.   for (i = 1; i < fCount; i += i);
  44.   m->maxIndex = i - 1;
  45.   m->maxCount = m->maxIndex - (m->maxIndex >> 2); /* Max fill 87.5 % */
  46.   m->count = 0;
  47.   m->table = (STEPtr) malloc((unsigned)((m->maxIndex+1) * sizeof(STE)));
  48.   for (i = 0; i <= m->maxIndex ; i++) {
  49.     m->table[i].key = NIL;
  50.   }
  51. #ifdef lint
  52.   SetCheckOutHashTable(m);
  53. #endif  
  54. #ifdef DEBUGSET
  55.   SetCheckOutHashTable(m);
  56. #endif DEBUGSET
  57.   return(m);
  58. }
  59.  
  60. void Set_Destroy(m)
  61. register Set m;
  62. {
  63.   if (m == (Set) NULL) return;
  64. #ifdef DEBUGSET
  65.   SetCheckOutHashTable(m);
  66. #endif DEBUGSET
  67.   free((char *)m->table);
  68.   free((char *)m);
  69. }
  70.  
  71. static void ExpandHashTable(m)
  72. register Set m;
  73. {
  74.   register STE *nh, *oe, *ne;
  75.   register int oldHashTableSize = m->maxIndex + 1, i;
  76.   register int key;
  77.   int index;
  78.  
  79.   m->maxIndex = oldHashTableSize * 2 - 1;
  80.   m->maxCount = m->maxIndex - (m->maxIndex >> 2);
  81.   nh = (STEPtr) malloc((unsigned)(oldHashTableSize * 2 * sizeof(STE)));
  82.   for (i = 0; i <= m->maxIndex; i++) nh[i].key = NIL;
  83.   for (i = 0; i < oldHashTableSize; i++) {
  84.     oe = &m->table[i];
  85.     key = oe->key;
  86.     if (key == NIL) continue;
  87.     index = HASH(key, m);
  88.     while (1) {
  89.       ne = &nh[index];
  90.       if (ne->key == NIL) {
  91.     ne->key = oe->key;
  92.     break;
  93.       } else {
  94.         assert(ne->key !=key);
  95.     index++;
  96.     if (index > m->maxIndex) index = 0;
  97.       }
  98.     }
  99.   }
  100.   free((char *)m->table);
  101.   m->table = nh;
  102. #ifdef DEBUGSET
  103.   SetCheckOutHashTable(m);
  104. #endif DEBUGSET
  105. }
  106.  
  107. int Set_Lookup(m, key)
  108. register Set m;
  109. register int key;
  110. {
  111.   register int index = HASH(key, m);
  112.   register STEPtr e;
  113.  
  114. #ifdef DEBUGSET
  115.   SetCheckOutHashTable(m);
  116. #endif DEBUGSET
  117.   while (1) {
  118.     e = &m->table[index];
  119.     if (e->key == NIL) {        /* we did not find it */
  120.       return (0);
  121.     } else if (e->key == key) {
  122.       return (1);
  123.     }
  124.     if (++index > m->maxIndex) index = 0;
  125.   }
  126. }
  127.  
  128. void Set_Delete(m, key)
  129. register Set m;
  130. register int key;
  131. /* Remove the entry, if it is there */
  132. {
  133.   register int index = HASH(key, m);
  134.   register STEPtr e;
  135.  
  136.   while (1) {
  137.     e = &m->table[index];
  138.     if (e->key == NIL) {        /* we did not find it */
  139. #ifdef DEBUGSET
  140.       SetCheckOutHashTable(m);
  141. #endif DEBUGSET
  142.       return;
  143.     }
  144.     if (e->key == key) {
  145.       /* Found it, now remove it */
  146.       m->count--;
  147.       e->key = NIL;
  148.       while (1) {
  149.         /* rehash until we reach nil again */
  150.         if (++index > m->maxIndex) index = 0;
  151.         e = & m->table[index];
  152.         key = e->key;
  153.         if (key == NIL) {
  154. #ifdef DEBUGSET
  155.             SetCheckOutHashTable(m);
  156. #endif DEBUGSET
  157.         return;
  158.     }
  159.         /* rehashing is done by removing then reinserting */
  160.         e->key = NIL;
  161.         m->count--;
  162.         Set_Insert(m, key);
  163.       }
  164.     }
  165.     if (++index > m->maxIndex) index = 0;
  166.   }
  167. }
  168.  
  169. void Set_Insert(m, key)
  170. register Set m;
  171. register int key;
  172. {
  173.   register int index;
  174.   register STEPtr e;
  175.   assert(key != NIL);
  176.   if (m->count >= m->maxCount) ExpandHashTable(m);
  177.   index = HASH(key, m);
  178.   while (1) {
  179.     e = &m->table[index];
  180.     if (e->key == NIL) {        /* put it here */
  181.       e->key = key;
  182.       m->count++;
  183. #ifdef DEBUGSET
  184.       SetCheckOutHashTable(m);
  185. #endif DEBUGSET
  186.       return;
  187.     } else if (e->key == key) {
  188. #ifdef DEBUGSET
  189.       SetCheckOutHashTable(m);
  190. #endif DEBUGSET
  191.       return;
  192.     }
  193.     if (++index > m->maxIndex) index = 0;
  194.   }
  195. }
  196.  
  197. int Set_FindNext(m, startIndex, keyPtr)
  198. register Set m;
  199. int *startIndex;
  200. int *keyPtr;
  201. {
  202.   register int i;
  203.   register STEPtr e;
  204.   if (m == NULL) return(0);
  205.   for (i = *startIndex; i <= m->maxIndex; i++) {
  206.     e = &m->table[i];
  207.     if (e->key != NIL) {
  208.       *keyPtr = e->key;
  209.       *startIndex = i + 1;
  210.       return(1);
  211.     }
  212.   }
  213.   *keyPtr = NIL;
  214.   *startIndex = -1;
  215.   return(0);
  216. }
  217.  
  218. void Set_Merge(from, to)
  219. Set from, to;
  220. {
  221.   int k;
  222.   Set_For(k, from)
  223.     Set_Insert(to, k);
  224.   Set_Next
  225. }
  226.  
  227. void Set_Print(m)
  228. register Set m;
  229. {
  230.     int key, index;
  231.     printf(
  232.         "\nDump of set @ 0x%05x, %d entr%s, current max %d\nIndex\tKey\n",
  233.     m, m->count, m->count == 1 ? "y" : "ies",  m->maxCount);
  234.     for (index = 0; index <= m->maxIndex; index++) {
  235.         key = m->table[index].key;
  236.     printf("%3d\t0x%08.8x\n", index, key);
  237.     }
  238. }
  239.  
  240. static void SetCheckOutHashTable(m)
  241. register Set m;
  242. {
  243.   register int i;
  244.   register STEPtr realElement, e;
  245.   register int index, firstIndex, count;
  246.   count = 0;
  247.  
  248.   for (i = 0; i <= m->maxIndex; i++) {
  249.     realElement = &m->table[i];
  250.     if (realElement->key != NIL) {
  251.       count++;
  252.       index = HASH(realElement->key, m);
  253.       firstIndex = index;
  254.       while (1) {
  255.     e = &m->table[index];
  256.     if (e->key == NIL) {        /* we did not find it */
  257.       break;
  258.     } else if (e->key == realElement->key) {
  259.       break;
  260.     } else {
  261.       index++;
  262.       if (index > m->maxIndex) index = 0;
  263.       if (index == firstIndex) {
  264.         index = -1;
  265.         break;
  266.       }
  267.     }
  268.       }
  269.       
  270.       if (index == -1 || e->key != realElement->key) {
  271.       fprintf(stderr,
  272.         "Set problem: Key 0x%x, rightIndex %d, realIndex %d\n",
  273.         realElement->key, firstIndex, index);
  274.           Set_Print(m);
  275.       }
  276.     }
  277.   }  
  278.   if (count != m->count) {
  279.     fprintf(stderr,
  280.       "Set problem: Should have %d entries, but found %d.\n", m->count,
  281.       count);
  282.     Set_Print(m);
  283.   }
  284. }
  285.